Łańcuch
Limit pamięci: 32 MB
Bajtocja nie zawsze była państwem demokratycznym.
W jej historii były również czarne karty.
Pewnego razu, generał Bajtelski -
przywódca junty żelazną ręką rządzącej Bajtocją -
postanowił zakończyć stan wojenny, trwający od momentu przejęcia
władzy, i zwolnić więzionych działaczy opozycji.
Nie chciał jednak uwolnić przywódcy opozycji Bajtazara.
Postanowił przykuć go do murów więzienia za pomocą
bajtockiego łańcucha.
Bajtocki łańcuch składa się z połączonych ze sobą ogniw oraz
przymocowanego do muru pręta.
Choć ogniwa nie są połączone z prętem, to bardzo trudno jest
je z niego zdjąć.
- Generale, czemuś mnie przykuł do murów więzienia, miast
uwolnić, jako to uczyniłeś z moimi kamratami! - wołał
Bajtazar.
- Ależ Bajtazarze, wszak nie jesteś przykuty i z pewnością
potrafisz sam zdjąć trzymające Cię ogniwa z pręta wystającego
z murów więzienia. -
przewrotnie stwierdził generał Bajtelski, po czym dodał -
Uporaj się z tym jednak przed godziną cyfracyjną i nie dzwoń
łańcuchami po nocy, gdyż w przeciwnym przypadku będę zmuszony
wezwać funkcjonariuszy Cyfronicji Obywatelskiej.
Pomóż Bajtazarowi!
Ponumerujmy kolejne ogniwa łańcucha liczbami .
Ogniwa te możemy zakładać i zdejmować z pręta zgodnie z
następującymi zasadami:
-
jednym ruchem możemy zdjąć lub założyć na pręt tylko jedno ogniwo,
-
ogniwo nr 1 można zawsze zdjąć lub założyć na pręt,
-
jeżeli ogniwa o numerach
(dla ) są zdjęte z pręta, a ogniwo nr jest
założone, to możemy zdjąć lub założyć ogniwo nr .
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia opis bajtockiego łańcucha,
-
obliczy minimalną liczbę ruchów, które należy wykonać,
aby zdjąć wszystkie ogniwa
bajtockiego łańcucha z pręta,
-
wypisze wynik na standardowe wyjście1.
Wejście
W pierwszym wierszu standardowego wejścia zapisano jedną
dodatnią liczbę całkowitą , .
W drugim wierszu zapisano liczb całkowitych
pooddzielanych pojedynczymi
odstępami.
Jeśli , to ogniwo nr jest założone na pręt, a jeśli
, to jest z niego zdjęte.
Wyjście
Pierwszy wiersz standardowego wejścia powinien zawierać
jedną liczbę całkowitą, równą minimalnej liczbie ruchów
potrzebnych do zdjęcia wszystkich ogniw bajtockiego łańcucha
z pręta.
Przykład
Dla danych wejściowych:
4
1 0 1 0
poprawną odpowiedzią jest:
6
Autor zadania: Marcin Kubica.